home *** CD-ROM | disk | FTP | other *** search
/ Delphi Programmer's Power Pack / Delphi Volume 1.iso / s_to_z / t_rex10 / regexp.c < prev    next >
Text File  |  1996-09-15  |  40KB  |  1,189 lines
  1. /************************************************\
  2. *                                                *
  3. *   REGEXP.DDL Implementation Module             *
  4. *   Copyright (c) 1996 by Prodigy Computing      *
  5. *   Copyright (c) 1992 by Borland International  *
  6. *   Copyright (c) 1986 by Univerisity of Toronto *
  7. *                                                *
  8. \************************************************/
  9.  
  10. /* This file was originally written by Henry Spencer for
  11.  * the University of Toronto and was modified by
  12.  * Borland International to compile with Borland C++ 3.1
  13.  * and for use in a DLL. Vincent Risi added the handling
  14.  * of the escapes \t \r \n \b \f for Prodigy Computing.
  15.  */
  16.  
  17. #include <stdio.h>
  18. #include <string.h>
  19.  
  20. #include "_regexp.h"
  21.  
  22. /*
  23.  * The "internal use only" fields in regexp.h are present to pass info from
  24.  * compile to execute that permits the execute phase to run lots faster on
  25.  * simple cases.  They are:
  26.  *
  27.  * regstart     char that must begin a match; '\0' if none obvious
  28.  * reganch      is the match anchored (at beginning-of-line only)?
  29.  * regmust      string (pointer into program) that match must include, or NULL
  30.  * regmlen      length of regmust string
  31.  *
  32.  * Regstart and reganch permit very fast decisions on suitable starting points
  33.  * for a match, cutting down the work a lot.  Regmust permits fast rejection
  34.  * of lines that cannot possibly match.  The regmust tests are costly enough
  35.  * that regcomp() supplies a regmust only if the r.e. contains something
  36.  * potentially expensive (at present, the only such thing detected is * or +
  37.  * at the start of the r.e., which can involve a lot of backup).  Regmlen is
  38.  * supplied because the test in regexec() needs it and regcomp() is computing
  39.  * it anyway.
  40.  */
  41.  
  42. /*
  43.  * Structure for regexp "program".  This is essentially a linear encoding
  44.  * of a nondeterministic finite-state machine (aka syntax charts or
  45.  * "railroad normal form" in parsing technology).  Each node is an opcode
  46.  * plus a "next" pointer, possibly plus an operand.  "Next" pointers of
  47.  * all nodes except BRANCH implement concatenation; a "next" pointer with
  48.  * a BRANCH on both ends of it is connecting two alternatives.  (Here we
  49.  * have one of the subtle syntax dependencies:  an individual BRANCH (as
  50.  * opposed to a collection of them) is never concatenated with anything
  51.  * because of operator precedence.)  The operand of some types of node is
  52.  * a literal string; for others, it is a node leading into a sub-FSM.  In
  53.  * particular, the operand of a BRANCH node is the first node of the branch.
  54.  * (NB this is *not* a tree structure:  the tail of the branch connects
  55.  * to the thing following the set of BRANCHes.)  The opcodes are:
  56.  */
  57.  
  58. /* definition   number  opnd?   meaning */
  59. #define END     0       /* no   End of program. */
  60. #define BOL     1       /* no   Match "" at beginning of line. */
  61. #define EOL     2       /* no   Match "" at end of line. */
  62. #define ANY     3       /* no   Match any one character. */
  63. #define ANYOF   4       /* str  Match any character in this string. */
  64. #define ANYBUT  5       /* str  Match any character not in this string. */
  65. #define BRANCH  6       /* node Match this alternative, or the next... */
  66. #define BACK    7       /* no   Match "", "next" ptr points backward. */
  67. #define EXACTLY 8       /* str  Match this string. */
  68. #define NOTHING 9       /* no   Match empty string. */
  69. #define STAR    10      /* node Match this (simple) thing 0 or more times. */
  70. #define PLUS    11      /* node Match this (simple) thing 1 or more times. */
  71. #define OPEN    20      /* no   Mark this point in input as start of #n. */
  72.                         /*      OPEN+1 is number 1, etc. */
  73. #define CLOSE   30      /* no   Analogous to OPEN. */
  74.  
  75. /*
  76.  * Opcode notes:
  77.  *
  78.  * BRANCH       The set of branches constituting a single choice are hooked
  79.  *              together with their "next" pointers, since precedence prevents
  80.  *              anything being concatenated to any individual branch.  The
  81.  *              "next" pointer of the last BRANCH in a choice points to the
  82.  *              thing following the whole choice.  This is also where the
  83.  *              final "next" pointer of each individual branch points; each
  84.  *              branch starts with the operand node of a BRANCH node.
  85.  *
  86.  * BACK         Normal "next" pointers all implicitly point forward; BACK
  87.  *              exists to make loop structures possible.
  88.  *
  89.  * STAR,PLUS    '?', and complex '*' and '+', are implemented as circular
  90.  *              BRANCH structures using BACK.  Simple cases (one character
  91.  *              per match) are implemented with STAR and PLUS for speed
  92.  *              and to minimize recursive plunges.
  93.  *
  94.  * OPEN,CLOSE   ...are numbered at compile time.
  95.  */
  96.  
  97. /*
  98.  * A node is one char of opcode followed by two chars of "next" pointer.
  99.  * "Next" pointers are stored as two 8-bit pieces, high order first.  The
  100.  * value is a positive offset from the opcode of the node containing it.
  101.  * An operand, if any, simply follows the node.  (Note that much of the
  102.  * code generation knows about this implicit relationship.)
  103.  *
  104.  * Using two bytes for the "next" pointer is vast overkill for most things,
  105.  * but allows patterns to get big without disasters.
  106.  */
  107. #define OP(p)   (*(p))
  108. #define NEXT(p) (((*((p)+1)&0377)<<8) + (*((p)+2)&0377))
  109. #define OPERAND(p)      ((p) + 3)
  110.  
  111. /*
  112.  * See _regex.h for one further detail of program structure.
  113.  */
  114.  
  115.  
  116. /*
  117.  * Utility definitions.
  118.  */
  119. #ifndef CHARBITS
  120. #define UCHARAT(p)      ((int)*(unsigned char *)(p))
  121. #else
  122. #define UCHARAT(p)      ((int)*(p)&CHARBITS)
  123. #endif
  124.  
  125. #define FAIL(m) { regerror = m; return(NULL); }
  126. #define ISMULT(c)       ((c) == '*' || (c) == '+' || (c) == '?')
  127. #define META    "^$.[()|?+*\\"
  128.  
  129. /*
  130.  * Flags to be passed up and down.
  131.  */
  132. #define HASWIDTH        01      /* Known never to match null string. */
  133. #define SIMPLE          02      /* Simple enough to be STAR/PLUS operand. */
  134. #define SPSTART         04      /* Starts with * or +. */
  135. #define WORST           0       /* Worst case. */
  136.  
  137. /*
  138.  * Global work variables for regcomp().
  139.  */
  140. static const char *regparse;    /* Input-scan pointer. */
  141. static int regnpar;                     /* () count. */
  142. static char regdummy;
  143. static char *regcode;               /* Code-emit pointer; ®dummy = don't. */
  144. static long regsize;                /* Code size. */
  145.  
  146. /*
  147.  * Forward declarations for regcomp()'s friends.
  148.  */
  149. #ifndef STATIC
  150. #define STATIC  static
  151. #endif
  152. STATIC char *reg();
  153. STATIC char *regbranch();
  154. STATIC char *regpiece();
  155. STATIC char *regatom();
  156. STATIC char *regnode();
  157. STATIC char *regnext();
  158. STATIC void regc();
  159. STATIC void reginsert();
  160. STATIC void regtail();
  161. STATIC void regoptail();
  162. #ifdef STRCSPN
  163. STATIC int strcspn();
  164. #endif
  165.  
  166. int regerror;
  167.  
  168. /*
  169.  - regcomp - compile a regular expression into internal code
  170.  *
  171.  * We can't allocate space until we know how big the compiled form will be,
  172.  * but we can't compile it (and thus know how big it is) until we've got a
  173.  * place to put the code.  So we cheat:  we compile it twice, once with code
  174.  * generation turned off and size counting turned on, and once "for real".
  175.  * This also means that we don't allocate space until we are sure that the
  176.  * thing really will compile successfully, and we never have to move the
  177.  * code and thus invalidate pointers into it.  (Note that it has to be in
  178.  * one piece because free() must be able to free it all.)
  179.  *
  180.  * Beware that the optimization-preparation code in here knows about some
  181.  * of the structure of the compiled regexp.
  182.  */
  183. regexp *regcomp(const char *exp)
  184. {
  185.         register regexp *r;
  186.         register char *scan;
  187.         register char *longest;
  188.         register int len;
  189.         int flags;
  190.         extern char *malloc();
  191.  
  192.         if (exp == NULL)
  193.                 FAIL(RE_INVALIDPARAMETER);
  194.  
  195.         /* First pass: determine size, legality. */
  196.         regparse = exp;
  197.         regnpar = 1;
  198.         regsize = 0L;
  199.         regcode = ®dummy;
  200.         regc(MAGIC);
  201.         if (reg(0, &flags) == NULL)
  202.